package com.xuyuan.arithmetic.datastructure.quest;

import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * 回溯算法
 * 思路：先构思树形结构图，再加过滤条件筛选满足条件的结构，递归求解。
 *
 * @author xuyuan
 */
public class BackTrackSolution {
    @Test
    public void test() {
        // System.out.println(combine(4, 2));
        // System.out.println(combinationSumWithNoRepeat(new int[]{2, 3, 5}, 8));
        // System.out.println(permuteUnique(new int[]{1, 2, 2}));
        List<List<String>> tickets = new ArrayList<>();
        tickets.add(Arrays.asList("JFK", "SFO"));
        tickets.add(Arrays.asList("JFK", "ATL"));
        tickets.add(Arrays.asList("SFO", "ATL"));
        tickets.add(Arrays.asList("ATL", "JFK"));
        tickets.add(Arrays.asList("ATL", "SFO"));
        System.out.println(findItinerary(tickets));
    }

    /**
     * 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
     */
    List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> combineResult = new ArrayList<>();
        LinkedList<Integer> combinePath = new LinkedList<>();
        combineHelper(combineResult, combinePath, n, k, 1);
        return combineResult;
    }

    /**
     * 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex
     *
     * @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。
     */
    private void combineHelper(List<List<Integer>> combineResult, LinkedList<Integer> combinePath, int n, int k, int startIndex) {
        // 终止条件
        if (combinePath.size() == k) {
            combineResult.add(new ArrayList<>(combinePath));
            return;
        }
        // i<=n 有些多余的递归过程，n - (k - combinePath.size()) + 1 临界位置，再往下没有意义.通过剪枝过滤多余的递归
        for (int i = startIndex; i <= n - (k - combinePath.size()) + 1; i++) {
            combinePath.add(i);
            combineHelper(combineResult, combinePath, n, k, i + 1);
            combinePath.removeLast();
        }
    }

    /**
     * [1,2,3,4,5,6,7,8,9]这个集合中找到和为n的k个数的组合
     */
    List<List<Integer>> combinationSum(int k, int n) {
        List<List<Integer>> combineResult = new ArrayList<>();
        LinkedList<Integer> combinePath = new LinkedList<>();
        combinationSumHelper(combineResult, combinePath, k, n, 1, 0);
        return combineResult;
    }

    private void combinationSumHelper(List<List<Integer>> combineResult, LinkedList<Integer> combinePath, int k, int n, int startIndex, int sum) {
        if (combinePath.size() == k && sum == n) {
            combineResult.add(new ArrayList<>(combinePath));
            return;
        }
        for (int i = startIndex; i <= 9 - (k - combinePath.size()) + 1; i++) {
            if (sum + i > n) return;
            combinePath.add(i);
            combinationSumHelper(combineResult, combinePath, k, n, i + 1, sum + i);
            combinePath.removeLast();
        }
    }


    /**
     * 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
     * 2 对应 "abc"
     * 3 对应 "def"
     * 4 对应 "ghi"
     * 5 对应 "jkl"
     * 6 对应 "mno"
     * 7 对应 "pqrs"
     * 8 对应 "tuv"
     * 9 对应 "wxyz"
     * 示例:
     * 输入："23"
     * 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
     * 输入："2"
     * 输出：["a","b","c"]
     */
    List<String> letterCombinationsWithRepeat(String digits) {
        List<String> letterCombinationResult = new ArrayList<>();
        if (digits == null || digits.length() == 0) return letterCombinationResult;
        StringBuilder temp = new StringBuilder();
        // 初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
        String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        // 迭代处理
        letterCombinationsHelper(letterCombinationResult, temp, digits, numString, 0);
        return letterCombinationResult;
    }

    private void letterCombinationsHelper(List<String> letterCombinationResult, StringBuilder temp, String digits, String[] numString, int length) {
        // 遍历全部一次记录一次得到的字符串
        if (length == digits.length()) {
            letterCombinationResult.add(temp.toString());
            return;
        }
        // str 表示当前num对应的字符串
        String str = numString[digits.charAt(length) - '0'];
        for (int i = 0; i < str.length(); i++) {
            temp.append(str.charAt(i));
            // 递归，处理下一层
            letterCombinationsHelper(letterCombinationResult, temp, digits, numString, length + 1);
            // 剔除末尾的继续尝试
            temp.deleteCharAt(temp.length() - 1);
        }
    }

    /**
     * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的数字可以无限制重复被选取。
     * 所有数字（包括 target）都是正整数。
     * 解集不能包含重复的组合。
     * <p>
     * 示例 1：
     * 输入：candidates = [2,3,6,7], target = 7,
     * 所求解集为： [ [7], [2,2,3] ]
     * <p>
     * 示例 2：
     * 输入：candidates = [2,3,5], target = 8,
     * 所求解集为： [ [2,2,2,2], [2,3,3], [3,5] ]
     */
    List<List<Integer>> combinationSum1(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        combinationSumHelper(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    private void combinationSumHelper(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            combinationSumHelper(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1);
        }
    }

    /**
     * 给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
     * candidates 中的每个数字在每个组合中只能使用一次。
     */
    List<List<Integer>> combinationSumWithNoRepeat(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        combinationSumHelperithNoRepeat(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    private void combinationSumHelperithNoRepeat(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            combinationSumHelperithNoRepeat(res, path, candidates, target, sum + candidates[i], i + 1);
            path.remove(path.size() - 1);
        }
    }

    /**
     * TODO 动态规划之后
     * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
     * 示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
     */
    List<List<String>> partition(String s) {
        return null;
    }

    /**
     * TODO
     * 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
     * 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
     * <p>
     * 示例 1：
     * 输入：s = "25525511135"
     * 输出：["255.255.11.135","255.255.111.35"]
     * <p>
     * 示例 2：
     * 输入：s = "0000"
     * 输出：["0.0.0.0"]
     * <p>
     * 示例 3：
     * 输入：s = "1111"
     * 输出：["1.1.1.1"]
     * <p>
     * 示例 4：
     * 输入：s = "010010"
     * 输出：["0.10.0.10","0.100.1.0"]
     * <p>
     * 示例 5：
     * 输入：s = "101023"
     * 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
     * <p>
     * 提示：
     * 0 <= s.length <= 3000
     * s 仅由数字组成
     */
    List<String> restoreIpAddresses(String s) {
        return null;
    }

    /**
     * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     * 说明：解集不能包含重复的子集。
     * 示例: 输入: nums = [1,2,3] 输出: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ]
     */
    List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) {
            subsetsHelper(res, new ArrayList<>(), nums, 0, i);
        }
        return res;
    }

    private void subsetsHelper(List<List<Integer>> res, List<Integer> path, int[] nums, int idx, int length) {
        if (path.size() == length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = idx; i < nums.length; i++) {
            path.add(nums[i]);
            subsetsHelper(res, path, nums, i + 1, length);
            path.remove(path.size() - 1);
        }
    }

    List<List<Integer>> subsets1(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        subsetsHelper1(res, path, nums, 0);
        return res;
    }

    private void subsetsHelper1(List<List<Integer>> res, LinkedList<Integer> path, int[] nums, int startIndex) {
        //「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
        res.add(new ArrayList<>(path));
        // 终止条件可不加
        if (startIndex >= nums.length) return;
        for (int i = startIndex; i < nums.length; i++) {
            path.add(nums[i]);
            subsetsHelper1(res, path, nums, i + 1);
            path.removeLast();
        }
    }

    /**
     * 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     * 说明：解集不能包含重复的子集。
     * <p>
     * 示例:
     * 输入: [1,2,2]
     * 输出: [ [2], [1], [1,2,2], [2,2], [1,2], []
     */
    List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        subsetsWithDupHelper(res, new LinkedList<>(), new boolean[nums.length], nums, 0);
        return res;
    }

    private void subsetsWithDupHelper(List<List<Integer>> res, LinkedList<Integer> path, boolean[] used, int[] nums, int startIndex) {
        res.add(new ArrayList<>(path));
        for (int i = startIndex; i < nums.length; i++) {
            // used用于标识同层的元素是否已经使用过
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            path.add(nums[i]);
            used[i] = true;
            subsetsWithDupHelper(res, path, used, nums, i + 1);
            used[i] = false;
            path.removeLast();
        }
    }

    /**
     * 给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
     */
    List<List<Integer>> findSubsequences(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length <= 1) return res;
        findSubsequencesHelper(res, new LinkedList<>(), nums, 0);
        return res;
    }

    private void findSubsequencesHelper(List<List<Integer>> res, LinkedList<Integer> path, int[] nums, int startIndex) {
        if (path.size() > 1) {
            res.add(new ArrayList<>(path));
        }
        Set<Integer> hs = new HashSet<>();
        for (int i = startIndex; i < nums.length; i++) {
            // 同层有相同元素，剪枝/不是递增剪枝
            if (!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i])) continue;
            hs.add(nums[i]);
            path.add(nums[i]);
            findSubsequencesHelper(res, path, nums, i + 1);
            path.removeLast();
        }
    }

    /**
     * 给定一个 没有重复 数字的序列，返回其所有可能的全排列。
     * <p>
     * 示例:
     * 输入: [1,2,3]
     * 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
     */
    List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length <= 1) return res;
        permuteHelper(res, new LinkedList<>(), new boolean[nums.length], nums);
        return res;
    }

    private void permuteHelper(List<List<Integer>> res, LinkedList<Integer> path, boolean[] used, int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.add(nums[i]);
            used[i] = true;
            permuteHelper(res, path, used, nums);
            used[i] = false;
            path.removeLast();
        }
    }

    private void permuteHelper(List<List<Integer>> res, LinkedList<Integer> path, int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (path.contains(nums[i])) continue;
            path.add(nums[i]);
            permuteHelper(res, path, nums);
            path.removeLast();
        }
    }

    /**
     * TODO
     * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
     * <p>
     * 示例 1：
     * 输入：nums = [1,1,2]
     * 输出： [[1,1,2], [1,2,1], [2,1,1]]
     * <p>
     * 示例 2：
     * 输入：nums = [1,2,3]
     * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
     */
    List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length <= 1) return res;
        Arrays.sort(nums);
        permuteUniqueHelper(res, new LinkedList<>(), new boolean[nums.length], nums);
        return res;
    }

    private void permuteUniqueHelper(List<List<Integer>> res, LinkedList<Integer> path, boolean[] used, int[] nums) {
        if (path.size() == nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            // 如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                used[i] = true;// 标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
                path.add(nums[i]);
                permuteUniqueHelper(res, path, used, nums);
                path.remove(path.size() - 1);// 回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                used[i] = false;// 回溯
            }
        }
    }

    /**
     * TODO
     * 给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。
     * 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。
     * <p>
     * 提示：
     * 如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前
     * 所有的机场都用三个大写字母表示（机场代码）。
     * 假定所有机票至少存在一种合理的行程。
     * 所有的机票必须都用一次 且 只能用一次。
     * <p>
     * 示例 1：
     * 输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
     * 输出：["JFK", "MUC", "LHR", "SFO", "SJC"]
     * <p>
     * 示例 2：
     * 输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
     * 输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
     * 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。
     */
    List<String> findItinerary(List<List<String>> tickets) {
        LinkedList<String> res = new LinkedList<>();
        LinkedList<String> path = new LinkedList<>();
        Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
        path.add("JFK");
        findItineraryHelper(res, path, tickets, new boolean[tickets.size()]);
        return res;
    }

    private boolean findItineraryHelper(LinkedList<String> res, LinkedList<String> path, List<List<String>> tickets, boolean[] used) {
        if (path.size() == tickets.size() + 1) {
            // 返回的是原有引用res = new LinkedList<>(path),res = path;
            res.addAll(path);
            return true;
        }
        for (int i = 0; i < tickets.size(); i++) {
            if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
                path.add(tickets.get(i).get(1));
                used[i] = true;
                if (findItineraryHelper(res, path, tickets, used)) {
                    return true;
                }
                used[i] = false;
                path.removeLast();
            }
        }
        return false;
    }

    /**
     * TODO
     * n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。任意两个皇后都不能处于同一行、同一列或同一斜线上
     * 给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
     * 每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
     */
    List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();
        char[][] chessboard = new char[n][n];
        for (char[] c : chessboard) {
            Arrays.fill(c, '.');
        }
        solveNQueensHelper(res, n, 0, chessboard);
        return res;
    }

    private void solveNQueensHelper(List<List<String>> res, int n, int row, char[][] chessboard) {
        if (row == n) {
            res.add(Array2List(chessboard));
            return;
        }

        for (int col = 0; col < n; ++col) {
            if (isValid(row, col, n, chessboard)) {
                chessboard[row][col] = 'Q';
                solveNQueensHelper(res, n, row + 1, chessboard);
                chessboard[row][col] = '.';
            }
        }

    }

    private List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    private boolean isValid(int row, int col, int n, char[][] chessboard) {
        // 检查列
        for (int i = 0; i < row; ++i) { // 相当于剪枝
            if (chessboard[i][col] == 'Q') {
                return false;
            }
        }

        // 检查45度对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (chessboard[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    // 方法2
    public List<List<String>> solveNQueens1(int n) {
        List<List<String>> res = new ArrayList<>();
        boolean[] usedCol = new boolean[n];                  // 列方向的直线条数为 n
        boolean[] usedDiag45 = new boolean[2 * n - 1];       // 45°方向的斜线条数为 2 * n - 1
        boolean[] usedDiag135 = new boolean[2 * n - 1];      // 135°方向的斜线条数为 2 * n - 1
        // 用于收集结果, 元素的index表示棋盘的row，元素的value代表棋盘的column
        int[] board = new int[n];
        solveNQueensHelper1(res, board, n, 0, usedCol, usedDiag45, usedDiag135);
        return res;
    }

    private void solveNQueensHelper1(List<List<String>> res, int[] board, int n, int row, boolean[] usedCol, boolean[] usedDiag45, boolean[] usedDiag135) {
        if (row == n) {
            // 收集结果
            List<String> temp = new ArrayList<>();
            for (int i : board) {
                char[] str = new char[n];
                Arrays.fill(str, '.');
                str[i] = 'Q';
                temp.add(new String(str));
            }
            res.add(temp);
            return;
        }

        for (int col = 0; col < n; col++) {
            if (usedCol[col] | usedDiag45[row + col] | usedDiag135[row - col + n - 1]) {
                continue;
            }
            board[row] = col;
            // 标记该列出现过
            usedCol[col] = true;
            // 同一45°斜线上元素的row + col为定值, 且各不相同
            usedDiag45[row + col] = true;
            // 同一135°斜线上元素row - col为定值, 且各不相同
            // row - col 值有正有负, 加 n - 1 是为了对齐零点
            usedDiag135[row - col + n - 1] = true;
            // 递归
            solveNQueensHelper1(res, board, n, row + 1, usedCol, usedDiag45, usedDiag135);
            usedCol[col] = false;
            usedDiag45[row + col] = false;
            usedDiag135[row - col + n - 1] = false;
        }
    }

    /**
     * TODO
     * 编写一个程序，通过填充空格来解决数独问题。
     * 一个数独的解法需遵循如下规则： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 '.' 表示。
     * <p>
     * 提示：
     * 给定的数独序列只包含数字 1-9 和字符 '.' 。
     * 你可以假设给定的数独只有唯一解。
     * 给定数独永远是 9x9 形式的
     */
    void solveSudoku(char[][] board) {
        solveSudokuHelper(board);
    }

    private boolean solveSudokuHelper(char[][] board) {
        //「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
        // 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
        for (int i = 0; i < 9; i++) { // 遍历行
            for (int j = 0; j < 9; j++) { // 遍历列
                if (board[i][j] != '.') { // 跳过原始数字
                    continue;
                }
                for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
                    if (isValidSudoku(i, j, k, board)) {
                        board[i][j] = k;
                        if (solveSudokuHelper(board)) { // 如果找到合适一组立刻返回
                            return true;
                        }
                        board[i][j] = '.';
                    }
                }
                // 9个数都试完了，都不行，那么就返回false
                return false;
                // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
            }
        }
        // 遍历完没有返回false，说明找到了合适棋盘位置了
        return true;
    }

    /**
     * 判断棋盘是否合法有如下三个维度:
     * 同行是否重复
     * 同列是否重复
     * 9宫格里是否重复
     */
    private boolean isValidSudoku(int row, int col, char val, char[][] board) {
        // 同行是否重复
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == val) {
                return false;
            }
        }
        // 同列是否重复
        for (int j = 0; j < 9; j++) {
            if (board[j][col] == val) {
                return false;
            }
        }
        // 9宫格里是否重复
        int startRow = (row / 3) * 3;
        int startCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == val) {
                    return false;
                }
            }
        }
        return true;
    }

    // 方法2
    public void solveSudoku2(char[][] board) {
        int[] rowBit = new int[9];
        int[] colBit = new int[9];
        int[] square9Bit = new int[9];
        // 1 10 11
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[y].length; x++) {
                int numBit = 1 << (board[y][x] - '1');
                rowBit[y] ^= numBit;
                colBit[x] ^= numBit;
                square9Bit[(y / 3) * 3 + x / 3] ^= numBit;
            }
        }
        solveSudokuHelper2(board, 0, rowBit, colBit, square9Bit);
    }

    public boolean solveSudokuHelper2(char[][] board, int n, int[] rowBit, int[] colBit, int[] square9Bit) {
        if (n >= 81) {
            return true;
        }
        // 快速算出行列编号 n/9 n%9
        int row = n / 9;
        int col = n % 9;

        if (board[row][col] != '.') {
            return solveSudokuHelper2(board, n + 1, rowBit, colBit, square9Bit);
        }

        for (char c = '1'; c <= '9'; c++) {
            int numBit = 1 << (c - '1');
            if (!isValid(numBit, row, col, rowBit, colBit, square9Bit)) continue;
            {
                board[row][col] = c;    // 当前的数字放入到数组之中，
                rowBit[row] ^= numBit; // 第一行rowBit[0],第一个元素eg: 1 , 0^1=1,第一个元素:4, 100^1=101,...
                colBit[col] ^= numBit;
                square9Bit[(row / 3) * 3 + col / 3] ^= numBit;
            }
            if (solveSudokuHelper2(board, n + 1, rowBit, colBit, square9Bit)) return true;
            {
                board[row][col] = '.';    // 不满足条件，回退成'.'
                rowBit[row] &= ~numBit; // 第一行rowBit[0],第一个元素eg: 1 , 101&=~1==>101&111111110==>100
                colBit[col] &= ~numBit;
                square9Bit[(row / 3) * 3 + col / 3] &= ~numBit;
            }
        }
        return false;
    }

    boolean isValid(int numBit, int row, int col, int[] rowBit, int[] colBit, int[] square9Bit) {
        // 左右
        if ((rowBit[row] & numBit) > 0) return false;
        // 上下
        if ((colBit[col] & numBit) > 0) return false;
        // 9宫格: 快速算出第n个九宫格,编号[0,8] , 编号=(row / 3) * 3 + col / 3
        if ((square9Bit[(row / 3) * 3 + col / 3] & numBit) > 0) return false;
        return true;
    }

}
